{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Longest Nice Substring"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #hash-table #string #divide-and-conquer #sliding-window"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #哈希表 #字符串 #分治 #滑动窗口"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: longestNiceSubstring"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最长的美好子字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>当一个字符串 <code>s</code> 包含的每一种字母的大写和小写形式 <strong>同时</strong> 出现在 <code>s</code> 中，就称这个字符串 <code>s</code> 是 <strong>美好</strong> 字符串。比方说，<code>\"abABB\"</code> 是美好字符串，因为 <code>'A'</code> 和 <code>'a'</code> 同时出现了，且 <code>'B'</code> 和 <code>'b'</code> 也同时出现了。然而，<code>\"abA\"</code> 不是美好字符串因为 <code>'b'</code> 出现了，而 <code>'B'</code> 没有出现。</p>\n",
    "\n",
    "<p>给你一个字符串 <code>s</code> ，请你返回 <code>s</code> 最长的 <strong>美好子字符串</strong> 。如果有多个答案，请你返回 <strong>最早</strong> 出现的一个。如果不存在美好子字符串，请你返回一个空字符串。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>s = \"YazaAay\"\n",
    "<b>输出：</b>\"aAa\"\n",
    "<strong>解释：</strong>\"aAa\" 是一个美好字符串，因为这个子串中仅含一种字母，其小写形式 'a' 和大写形式 'A' 也同时出现了。\n",
    "\"aAa\" 是最长的美好子字符串。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>s = \"Bb\"\n",
    "<b>输出：</b>\"Bb\"\n",
    "<b>解释：</b>\"Bb\" 是美好字符串，因为 'B' 和 'b' 都出现了。整个字符串也是原字符串的子字符串。</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>s = \"c\"\n",
    "<b>输出：</b>\"\"\n",
    "<b>解释：</b>没有美好子字符串。</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>s = \"dDzeE\"\n",
    "<b>输出：</b>\"dD\"\n",
    "<strong>解释：</strong>\"dD\" 和 \"eE\" 都是最长美好子字符串。\n",
    "由于有多个美好子字符串，返回 \"dD\" ，因为它出现得最早。</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= s.length <= 100</code></li>\n",
    "\t<li><code>s</code> 只包含大写和小写英文字母。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [longest-nice-substring](https://leetcode.cn/problems/longest-nice-substring/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [longest-nice-substring](https://leetcode.cn/problems/longest-nice-substring/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"YazaAay\"', '\"Bb\"', '\"c\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubstring(self, s: str) -> str:\n",
    "        def f1(a, b):\n",
    "            A = [0 for i in range(26)]\n",
    "            B = [0 for i in range(26)]\n",
    "            while a <= b:\n",
    "                ch = s[a]\n",
    "                if 'a' <= ch and ch <= 'z':\n",
    "                    diff = ord(ch) - ord('a')\n",
    "                    A[diff] += 1\n",
    "                else:\n",
    "                    diff = ord(ch) - ord('A')\n",
    "                    B[diff] += 1\n",
    "                a += 1\n",
    "            return f2(A, B)\n",
    "        def f2(A, B):\n",
    "            for i in range(26):\n",
    "                if A[i] == 0 and B[i] == 0:\n",
    "                    continue\n",
    "                elif A[i] > 0 and B[i] > 0:\n",
    "                    continue\n",
    "                else:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        sz = len(s)\n",
    "        result = \"\"\n",
    "        for i in range(sz):\n",
    "            for j in range(i + 1, sz):\n",
    "                diff = j - i + 1\n",
    "                if f1(i, j):\n",
    "                    if len(result) < diff:\n",
    "                        result = s[i:j + 1]\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def is_nice(self, substr):\n",
    "        return all(ch.swapcase() in substr for ch in substr)\n",
    "\n",
    "    def longestNiceSubstring(self, s: str) -> str:\n",
    "        longest = \"\"\n",
    "        for i in range(len(s)):\n",
    "            for j in range(i+1, len(s)+1):\n",
    "                substr = s[i:j]\n",
    "                if self.is_nice(substr) and len(substr) > len(longest):\n",
    "                    longest = substr\n",
    "        return longest\n",
    "    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubstring(self, s: str) -> str:\n",
    "        ans = ''\n",
    "        n = len(s)\n",
    "        for i in range(n):\n",
    "            for j in range(i,n+1):\n",
    "                m = s[i:j]\n",
    "                for z in m:\n",
    "                    if z.upper() not in m or z.lower() not in m:\n",
    "                        break\n",
    "                else:\n",
    "                    if len(m) > len(ans) :\n",
    "                        ans = m \n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubstring(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        maxPos, maxLen = 0, 0\n",
    "        for i in range(n):\n",
    "            lower, upper = 0, 0\n",
    "            for j in range(i, n):\n",
    "                if s[j].islower():\n",
    "                    lower |= 1 << (ord(s[j]) - ord('a'))\n",
    "                else:\n",
    "                    upper |= 1 << (ord(s[j]) - ord('A'))\n",
    "                if lower == upper and j - i + 1 > maxLen:\n",
    "                    maxPos = i\n",
    "                    maxLen = j - i + 1\n",
    "        return s[maxPos: maxPos + maxLen]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubstring(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        length = 0\n",
    "        flag = 0\n",
    "        if n< 2:\n",
    "            return \"\"\n",
    "        for i in range(n):\n",
    "            a, b = 0, 0\n",
    "            for j in range(i,n):\n",
    "                if s[j].islower():\n",
    "                    a |= 1 << (ord(s[j]) - ord('a'))\n",
    "                else:\n",
    "                    b |= 1 << (ord(s[j]) - ord('A'))\n",
    "                if a == b and j-i+1 > length:\n",
    "                    length = j - i + 1\n",
    "                    flag = i\n",
    "        return s[flag:flag+length]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubstring(self, s: str) -> str:\n",
    "        if len(s)<2:\n",
    "            return \"\"\n",
    "        for i,c in enumerate(s):\n",
    "            if c.upper() not in s or c.lower() not in s:\n",
    "                return max(self.longestNiceSubstring(s[:i]), self.longestNiceSubstring(s[i+1:]),key = len)\n",
    "        return s\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubstring(self, s: str) -> str:\n",
    "        # 暴力\n",
    "        n = len(s)\n",
    "        ans = ''\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n + 1):\n",
    "                set_ = set(s[i:j])\n",
    "                for c in set_:\n",
    "                    if c.swapcase() not in set_:\n",
    "                        break\n",
    "                else:\n",
    "                    if j - i > len(ans):\n",
    "                        ans = s[i:j]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubstring(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        maxPos, maxLen = 0, 0\n",
    "        for i in range(n):\n",
    "            lower, upper = 0, 0\n",
    "            for j in range(i,n):\n",
    "                if s[j].islower():\n",
    "                    lower|=(1<<(ord(s[j])-ord('a')))\n",
    "                else:\n",
    "                    upper|=(1<<(ord(s[j])-ord('A')))\n",
    "                if upper==lower and j-i+1>maxLen:\n",
    "                    maxLen=j-i+1\n",
    "                    maxPos=i\n",
    "        return s[maxPos:maxPos+maxLen]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubstring(self, s: str) -> str:\n",
    "        n=len(s)\n",
    "        ans=''\n",
    "        for i in range(n):\n",
    "            for j in range(n-1,i,-1):\n",
    "                t=s[i:j+1]\n",
    "                f=0\n",
    "                for k in t:\n",
    "                    if not (chr(ord(k)+32) in t or chr(ord(k)-32) in t):\n",
    "                        f=-1\n",
    "                        break\n",
    "                if f==0:\n",
    "                    if (j-i+1)>len(ans):\n",
    "                        ans=t\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubstring(self, s: str) -> str:\n",
    "        if len(s) < 2: return \"\"\n",
    "        \n",
    "        res = \"\"\n",
    "        for i in range(len(s)):\n",
    "            chars = set()\n",
    "            for j in range(i, len(s)):\n",
    "                chars.add(s[j])\n",
    "                if len(chars) == 2 * len(set(x.lower() for x in chars)):\n",
    "                    if j - i + 1 > len(res):\n",
    "                        res = s[i:j+1]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubstring(self, s: str) -> str:\n",
    "        def check(typeNum):\n",
    "            nonlocal maxPos, maxLen\n",
    "            lowerCnt = [0] * 26\n",
    "            upperCnt = [0] * 26\n",
    "            l, r, total, cnt = 0, 0, 0, 0\n",
    "            while r < len(s):\n",
    "                idx = ord(s[r].lower()) - ord('a')\n",
    "                if s[r].islower():\n",
    "                    lowerCnt[idx] += 1\n",
    "                    if lowerCnt[idx] == 1 and upperCnt[idx] > 0:\n",
    "                        cnt += 1\n",
    "                else:\n",
    "                    upperCnt[idx] += 1\n",
    "                    if upperCnt[idx] == 1 and lowerCnt[idx] > 0:\n",
    "                        cnt += 1\n",
    "                if lowerCnt[idx] + upperCnt[idx] == 1:\n",
    "                    total += 1\n",
    "\n",
    "                while total > typeNum :\n",
    "                    idx = ord(s[l].lower()) - ord('a')\n",
    "                    if lowerCnt[idx] + upperCnt[idx] == 1:\n",
    "                        total -= 1\n",
    "                    if s[l].islower():\n",
    "                        lowerCnt[idx] -= 1\n",
    "                        if lowerCnt[idx] == 0 and upperCnt[idx] > 0:\n",
    "                            cnt -= 1\n",
    "                    else:\n",
    "                        upperCnt[idx] -= 1\n",
    "                        if upperCnt[idx] == 0 and lowerCnt[idx] > 0:\n",
    "                            cnt -= 1\n",
    "                    l += 1\n",
    "                if cnt == typeNum and r - l + 1 > maxLen:\n",
    "                    maxPos, maxLen = l, r - l + 1\n",
    "                r += 1\n",
    "        \n",
    "        maxPos, maxLen = 0, 0\n",
    "        types = len(set(s.lower()))\n",
    "        for i in range(1, types + 1):\n",
    "            check(i)\n",
    "        return s[maxPos: maxPos + maxLen]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubstring(self, s: str) -> str:\n",
    "        def isPerfect(t):\n",
    "            dic = Counter(t)\n",
    "            lst = []\n",
    "            for c in dic.keys():\n",
    "                if c.islower() and c.upper() not in dic:\n",
    "                    lst.append(c)\n",
    "                if c.isupper() and c.lower() not in dic:\n",
    "                    lst.append(c)\n",
    "            return not len(lst)\n",
    "\n",
    "        def useSetJudge(t):\n",
    "            set1 = set(t)\n",
    "            set2 = set(t.upper())\n",
    "            return len(set1) // len(set2) == 2\n",
    "\n",
    "        def check(t):\n",
    "            set_t = set(t)\n",
    "            for c in t:\n",
    "                if c.upper() not in set_t or c.lower() not in set_t:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        n = len(s)\n",
    "        ans = \"\"\n",
    "        m = 0\n",
    "        for i in range(n):\n",
    "            for j in range(n - 1, i, -1):\n",
    "                ss = s[i: j + 1]\n",
    "                if check(ss) and len(ss) > m:\n",
    "                    m = len(ss)\n",
    "                    ans = ss\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def is_nice(self, substr):\n",
    "        return all(ch.swapcase() in substr for ch in substr)\n",
    "\n",
    "    def longestNiceSubstring(self, s: str) -> str:\n",
    "        longest = \"\"\n",
    "        for i in range(len(s)):\n",
    "            for j in range(i+1, len(s)+1):\n",
    "                substr = s[i:j]\n",
    "                if self.is_nice(substr) and len(substr) > len(longest):\n",
    "                    longest = substr\n",
    "        return longest\n",
    "    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def is_nice(self, substr):\n",
    "        return all(ch.swapcase() in substr for ch in substr)\n",
    "\n",
    "    def longestNiceSubstring(self, s: str) -> str:\n",
    "        longest = \"\"\n",
    "        for i in range(len(s)):\n",
    "            for j in range(i+1, len(s)+1):\n",
    "                substr = s[i:j]\n",
    "                if self.is_nice(substr) and len(substr) > len(longest):\n",
    "                    longest = substr\n",
    "        return longest\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubstring(self, s: str) -> str:\n",
    "        def isPerfect(t):\n",
    "            dic = Counter(t)\n",
    "            lst = []\n",
    "            for c in dic.keys():\n",
    "                if c.islower() and c.upper() not in dic:\n",
    "                    lst.append(c)\n",
    "                if c.isupper() and c.lower() not in dic:\n",
    "                    lst.append(c)\n",
    "            return not len(lst)\n",
    "\n",
    "        def useSetJudge(t):\n",
    "            set1 = set(t)\n",
    "            set2 = set(t.upper())\n",
    "            return len(set1) // len(set2) == 2\n",
    "\n",
    "        n = len(s)\n",
    "        ans = \"\"\n",
    "        m = 0\n",
    "        for i in range(n):\n",
    "            for j in range(n - 1, i, -1):\n",
    "                ss = s[i: j + 1]\n",
    "                if useSetJudge(ss) and len(ss) > m:\n",
    "                    m = len(ss)\n",
    "                    ans = ss\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubstring(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        maxPos, maxLen = 0, 0\n",
    "        for i in range(n):\n",
    "            lower, upper = 0, 0\n",
    "            for j in range(i, n):\n",
    "                if s[j].islower():\n",
    "                    lower |= 1 << (ord(s[j]) - ord('a'))\n",
    "                else:\n",
    "                    upper |= 1 << (ord(s[j]) - ord('A'))\n",
    "                if lower == upper and j - i + 1 > maxLen:\n",
    "                    maxPos = i\n",
    "                    maxLen = j - i + 1\n",
    "        return s[maxPos: maxPos + maxLen]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubstring(self, s: str) -> str:\n",
    "        \n",
    "        for c in set(s):\n",
    "            if c.upper() not in s or c.lower() not in s:\n",
    "                max_s=''\n",
    "                for t in s.split(c):\n",
    "                    if len(self.longestNiceSubstring(t))>len(max_s):\n",
    "                        max_s=self.longestNiceSubstring(t)\n",
    "                return max_s\n",
    "        return s\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubstring(self, s: str) -> str:\n",
    "        if len(s) < 2:\n",
    "            return ''\n",
    "        x = set(s)\n",
    "        for i, c in enumerate(s):\n",
    "            if c.upper() not in x or c.lower() not in x:\n",
    "                return max(self.longestNiceSubstring(s[:i]), self.longestNiceSubstring(s[i+1:]), key=len)\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubstring(self, s: str) -> str:\n",
    "        if len(s)<2:\n",
    "            return \"\"\n",
    "        for i,c in enumerate(s):\n",
    "            if c.upper() not in s or c.lower() not in s:\n",
    "                return max(self.longestNiceSubstring(s[:i]),self.longestNiceSubstring(s[i+1:]),key=len)\n",
    "        return s            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubstring(self, s: str) -> str:\n",
    "        \n",
    "        for i in range(len(s) - 1, 0, -1):\n",
    "            for j in range(len(s) - i):\n",
    "                temp = s[j:j+i+1]\n",
    "                temp_dict = Counter(temp)\n",
    "                temp_set = set()\n",
    "                flag = True\n",
    "                for key in temp_dict:\n",
    "                    if key not in temp_set:\n",
    "                        temp_set.add(key.lower())\n",
    "                        if key.islower():\n",
    "                            key_ = key.upper()\n",
    "                        else:\n",
    "                            key_ = key.lower()\n",
    "                        if key_ not in temp_dict:\n",
    "                            flag = False\n",
    "                            break\n",
    "                if flag:\n",
    "                    return temp\n",
    "        return \"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubstring(self, s: str) -> str:\n",
    "        def check(a,b):\n",
    "            for i in range(26):\n",
    "                low = b[i] - a[i]\n",
    "                up = b[i + 32] - a[i + 32]\n",
    "                if (low != 0) and (up == 0): return False\n",
    "                if (low == 0) and (up != 0): return False\n",
    "            return True\n",
    "\n",
    "        n = len(s)\n",
    "        pre_cnt = [[0 for i in range(128)]]\n",
    "        for i in range(n):\n",
    "            pre_cnt.append(pre_cnt[i].copy())\n",
    "            pre_cnt[i+1][ord(s[i])-65] += 1\n",
    "        idx, length = 0, 0\n",
    "        for i in range(n):\n",
    "            for j in range(i+1,n):\n",
    "                if j-i+1 > length:\n",
    "                    a = pre_cnt[i]\n",
    "                    b = pre_cnt[j+1]\n",
    "                    if check(a,b): idx, length = i, j-i+1\n",
    "        return  '' if length == 0 else s[idx:idx+length]\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubstring(self, s: str) -> str:\n",
    "        def isPerfect(t):\n",
    "            dic = Counter(t)\n",
    "            lst = []\n",
    "            for c in dic.keys():\n",
    "                if c.islower() and c.upper() not in dic:\n",
    "                    lst.append(c)\n",
    "                if c.isupper() and c.lower() not in dic:\n",
    "                    lst.append(c)\n",
    "            return not len(lst)\n",
    "\n",
    "        n = len(s)\n",
    "        ans = \"\"\n",
    "        m = 0\n",
    "        for i in range(n):\n",
    "            for j in range(n - 1, i, -1):\n",
    "                ss = s[i: j + 1]\n",
    "                if isPerfect(ss) and len(ss) > m:\n",
    "                    m = len(ss)\n",
    "                    ans = ss\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubstring(self, s: str) -> str:\n",
    "        if len(s) < 2: return \"\"\n",
    "        for i, c in enumerate(s):\n",
    "            if c.upper() not in s or c.lower() not in s:\n",
    "                return max(self.longestNiceSubstring(s[:i]), self.longestNiceSubstring(s[i+1:]), key=len)\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubstring(self, s: str) -> str:\n",
    "        def judge(s):\n",
    "            for i in s:\n",
    "                if i.lower() not in s or i.upper() not in s:\n",
    "                    return False\n",
    "            return True\n",
    "        \n",
    "        for l in range(len(s),1,-1):\n",
    "            for idx in range(len(s)-l+1):\n",
    "                if judge(s[idx:idx+l]):\n",
    "                    return s[idx:idx+l]\n",
    "        return ''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubstring(self, s: str) -> str:\n",
    "        if len(s) < 2:\n",
    "            return \"\"\n",
    "        for i, c in enumerate(s):\n",
    "            if c.upper() not in s or c.lower() not in s:\n",
    "                return max(self.longestNiceSubstring(s[:i]), self.longestNiceSubstring(s[i+1:]), key = len)\n",
    "        return s\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubstring(self, s: str) -> str:\n",
    "        if len(s) < 2:\n",
    "            return \"\"\n",
    "        for i, c in enumerate(s):\n",
    "            # 存在任意不满足题目的割点\n",
    "            if c.swapcase() not in s:\n",
    "                return max(self.longestNiceSubstring(s[:i]), self.longestNiceSubstring(s[i+1:]), key = len)\n",
    "        return s\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubstring(self, s: str) -> str:\n",
    "        if len(s)<2:\n",
    "            return \"\"\n",
    "        for i,c in enumerate(s):\n",
    "            if c.upper() not in s or c.lower() not in s:\n",
    "                return max(self.longestNiceSubstring(s[:i]), self.longestNiceSubstring(s[i+1:]),key = len)\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubstring(self, s: str) -> str:\n",
    "        def isNice(substr: str):\n",
    "            if len(substr) < 2:\n",
    "                return False\n",
    "            m = dict()\n",
    "            for c in substr:\n",
    "                m[c] = m.get(c, 0) + 1\n",
    "            flag = True\n",
    "            for c in m.keys():\n",
    "                if (c.isupper() and m.get(c.lower(), 0) == 0) or (c.islower() and m.get(c.upper(), 0) == 0):\n",
    "                    flag = False\n",
    "            return flag\n",
    "\n",
    "        ans = ''\n",
    "        for i in range(len(s)):\n",
    "            for j in range(2, len(s) + 1):\n",
    "                substr = s[i:j]\n",
    "                if isNice(substr) and len(substr) > len(ans):\n",
    "                    ans = substr\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubstring(self, s: str) -> str:\n",
    "        n=len(s)\n",
    "        ans=''\n",
    "        for i in range(n):\n",
    "            for j in range(n-1,i,-1):\n",
    "                t=s[i:j+1]\n",
    "                f=0\n",
    "                for k in t:\n",
    "                    if not (chr(ord(k)+32) in t or chr(ord(k)-32) in t):\n",
    "                        f=-1\n",
    "                        break\n",
    "                if f==0:\n",
    "                    if (j-i+1)>len(ans):\n",
    "                        ans=t\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubstring(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        maxL, maxPos = 0, 0\n",
    "        for i in range(n):\n",
    "            lower, upper = 0, 0 \n",
    "            for j in range(i, n):\n",
    "                if s[j].islower():\n",
    "                    lower |= 1 << (ord(s[j]) - ord('a'))\n",
    "                else:\n",
    "                    upper |= 1 << ((ord(s[j]) - ord('A')))\n",
    "                if lower == upper and j -i + 1 > maxL:\n",
    "                    maxPos = i\n",
    "                    maxL = j - i + 1\n",
    "        return s[maxPos: maxPos + maxL]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubstring(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        k = 0\n",
    "        res = ''\n",
    "        for i in range(n):\n",
    "            for j in range(n-1, i, -1):\n",
    "                flag = True\n",
    "                for ch in s[i:j+1]:\n",
    "                    if ch.islower() and ch.upper() not in s[i:j+1] or \\\n",
    "                       ch.isupper() and ch.lower() not in s[i:j+1]:\n",
    "                        flag = False\n",
    "                        break\n",
    "                if flag and j - i > k:\n",
    "                    k = j - i\n",
    "                    res = s[i:j+1]\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubstring(self, s: str) -> str:\n",
    "        if not s:\n",
    "            return \"\"\n",
    "        for i in range(len(s)):\n",
    "            if (s[i].lower() not in s) or (s[i].upper() not in s):\n",
    "                return max(self.longestNiceSubstring(s[:i]),self.longestNiceSubstring(s[i+1:]),key=len)\n",
    "            if i==len(s)-1:\n",
    "                return s\n",
    "                \n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubstring(self, s: str) -> str:\n",
    "        if len(s) < 2:\n",
    "            return ''\n",
    "        for i, c in enumerate(s):\n",
    "            # 存在任意不满足题目的割点\n",
    "            if c.upper() not in s or c.lower() not in s:\n",
    "                return max(self.longestNiceSubstring(s[:i]), self.longestNiceSubstring(s[i+1:]), key = len)\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubstring(self, s: str) -> str:\n",
    "        maxPos, maxLen = 0, 0\n",
    "        def dfs(start, end):\n",
    "            nonlocal maxPos, maxLen\n",
    "            if start >= end:\n",
    "                return\n",
    "            lower, upper = 0, 0\n",
    "            for i in range(start, end + 1):\n",
    "                if s[i].islower():\n",
    "                    lower|= 1 << (ord(s[i]) - ord('a'))\n",
    "                else:\n",
    "                    upper|= 1 << (ord(s[i]) - ord('A'))\n",
    "            if lower == upper:\n",
    "                if end - start + 1 > maxLen:\n",
    "                    maxPos, maxLen = start, end - start + 1\n",
    "                return\n",
    "            pos, valid = start, lower & upper\n",
    "            while pos <= end:\n",
    "                start = pos\n",
    "                while pos <= end and valid & (1 << (ord(s[pos].lower()) - ord('a'))):\n",
    "                    pos += 1\n",
    "                dfs(start, pos - 1)\n",
    "                pos += 1\n",
    "        dfs(0, len(s) - 1)\n",
    "        return s[maxPos : maxPos + maxLen]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubstring(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        maxPos,maxLen = 0,0\n",
    "        for i in range(n):\n",
    "            lower,upper = 0,0\n",
    "            for j in range(i,n):\n",
    "                if s[j].islower():\n",
    "                    lower |= 1<<(ord(s[j])-ord('a'))\n",
    "                else:\n",
    "                    upper |= 1<<(ord(s[j])-ord('A'))\n",
    "                if lower==upper and j-i+1>maxLen:\n",
    "                    maxPos = i\n",
    "                    maxLen = j-i+1\n",
    "        return s[maxPos:maxPos+maxLen]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubstring(self, s: str) -> str:\n",
    "        def is_nice(sub):\n",
    "            return all(char.swapcase() in sub for char in sub)\n",
    "\n",
    "        longest = \"\"\n",
    "        for i in range(len(s)):\n",
    "            for j in range(i + 1, len(s)):\n",
    "                sub = s[i:j + 1]\n",
    "                if is_nice(sub) and len(sub) > len(longest):\n",
    "                    longest = sub\n",
    "        return longest"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubstring(self, s: str) -> str:\n",
    "        if len(s) <= 1:\n",
    "            return ''\n",
    "        for i, c in enumerate(s):\n",
    "            # 存在任意不满足题目的割点\n",
    "            if c.upper() not in s or c.lower() not in s:\n",
    "                #print(c)\n",
    "                #print(s[:i],s[i+1:])\n",
    "                return max(self.longestNiceSubstring(s[:i]), self.longestNiceSubstring(s[i+1:]), key = len)\n",
    "        return s\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubstring(self, s: str) -> str:\n",
    "        if len(s) < 2:\n",
    "            return \"\"\n",
    "\n",
    "        for i,j in enumerate(s):\n",
    "            if j.upper() not in s or j.lower() not in s:\n",
    "                return max(self.longestNiceSubstring(s[:i]),self.longestNiceSubstring(s[i+1:]),key = len)\n",
    "        return s\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 方法一\n",
    "# class Solution:\n",
    "#     def longestNiceSubstring(self, s: str) -> str:\n",
    "#         max_len = 0\n",
    "#         ret = \"\"\n",
    "#         def check(str_list):\n",
    "#             nonlocal max_len, ret\n",
    "#             for s in str_list:\n",
    "#                 if len(s) > 1:\n",
    "#                     s_set = set(s)\n",
    "#                     split_pos = []\n",
    "#                     for i in range(len(s)):\n",
    "#                         if s[i].lower() not in s_set or s[i].upper() not in s_set:\n",
    "#                             split_pos.append(i)\n",
    "#                     if not split_pos:\n",
    "#                         if len(s) > max_len:\n",
    "#                             ret = s\n",
    "#                             max_len = len(s)\n",
    "#                         return\n",
    "#                     new_str_list = []\n",
    "#                     last_i = 0\n",
    "#                     for pos in split_pos:\n",
    "#                         new_str_list.append(s[last_i: pos])\n",
    "#                         last_i = pos + 1\n",
    "#                     if last_i < len(s):  # 排除最后一个为分割点的\n",
    "#                         new_str_list.append(s[last_i:])\n",
    "#                     check(new_str_list)\n",
    "#         str_list = [s]\n",
    "#         check(str_list)\n",
    "#         return ret\n",
    "\n",
    "# 方法二\n",
    "class Solution:\n",
    "    def longestNiceSubstring(self, s: str) -> str:\n",
    "        if len(s) < 2:\n",
    "            return \"\"\n",
    "        for i, c in enumerate(s):\n",
    "            # 存在任意不满足题目的割点\n",
    "            if c.upper() not in s or c.lower() not in s:\n",
    "                return max(self.longestNiceSubstring(s[:i]), self.longestNiceSubstring(s[i+1:]), key = len)\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubstring(self, s: str) -> str:\n",
    "        maxPos, maxLen = 0, 0\n",
    "        def dfs(start, end):\n",
    "            nonlocal maxPos, maxLen\n",
    "            if start >= end:\n",
    "                return\n",
    "            lower, upper = 0, 0\n",
    "            for i in range(start, end + 1):\n",
    "                if s[i].islower():\n",
    "                    lower|= 1 << (ord(s[i]) - ord('a'))\n",
    "                else:\n",
    "                    upper|= 1 << (ord(s[i]) - ord('A'))\n",
    "            if lower == upper:\n",
    "                if end - start + 1 > maxLen:\n",
    "                    maxPos, maxLen = start, end - start + 1\n",
    "                return\n",
    "            pos, valid = start, lower & upper\n",
    "            while pos <= end:\n",
    "                start = pos\n",
    "                while pos <= end and valid & (1 << (ord(s[pos].lower()) - ord('a'))):\n",
    "                    pos += 1\n",
    "                dfs(start, pos - 1)\n",
    "                pos += 1\n",
    "        dfs(0, len(s) - 1)\n",
    "        return s[maxPos : maxPos + maxLen]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubstring(self, s: str) -> str:\n",
    "        if len(s) < 2:\n",
    "            return \"\"\n",
    "        for i, c in enumerate(s):\n",
    "            if c.upper() not in s or c.lower() not in s:\n",
    "                return max(self.longestNiceSubstring(s[:i]), self.longestNiceSubstring(s[i+1:]) , key = len)    \n",
    "        return s        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubstring(self, s: str) -> str:\n",
    "        if len(s) < 2:\n",
    "            return ''\n",
    "        for i, c in enumerate(s):\n",
    "            # 存在任意不满足题目的割点\n",
    "            if c.swapcase() not in s:\n",
    "                return max(self.longestNiceSubstring(s[:i]), self.longestNiceSubstring(s[i+1:]), key = len)\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubstring(self, s: str) -> str:\n",
    "        if len(s) < 2:\n",
    "            return \"\"\n",
    "        for i, c in enumerate(s):\n",
    "            # 存在任意不满足题目的割点\n",
    "            if c.upper() not in s or c.lower() not in s:\n",
    "                return max(self.longestNiceSubstring(s[:i]), self.longestNiceSubstring(s[i+1:]), key = len)\n",
    "        return s\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubstring(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        l, r = 0, -1\n",
    "\n",
    "        for i in range(n):\n",
    "            lower, upper = 0,0\n",
    "            for j in range(i, n):\n",
    "                if s[j].islower():\n",
    "                    lower |= (1 << ( ord(s[j]) - ord(\"a\") ))\n",
    "                else:\n",
    "                    upper |= (1 << ( ord(s[j]) - ord(\"A\") ))\n",
    "                if lower == upper and j-i+1 > r-l+1:\n",
    "                    l, r = i, j \n",
    "        \n",
    "        return s[l:r+1]\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubstring(self, s: str) -> str:\n",
    "        if len(s) < 2:\n",
    "            return \"\"\n",
    "        for i, c in enumerate(s):\n",
    "            # 存在任意不满足题目的割点\n",
    "            if c.upper() not in s or c.lower() not in s:\n",
    "                return max(self.longestNiceSubstring(s[:i]), self.longestNiceSubstring(s[i+1:]), key = len)\n",
    "        return s\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubstring(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        maxpos, maxlen = 0, 0\n",
    "        for i in range(n):\n",
    "            lower, upper = 0, 0\n",
    "            for j in range(i, n):\n",
    "                if s[j].islower():\n",
    "                    lower |= 1 << (ord(s[j]) - ord('a'))\n",
    "                else:\n",
    "                    upper |= 1 << (ord(s[j]) - ord('A'))\n",
    "                if lower == upper and j - i + 1 > maxlen:\n",
    "                    maxpos = i\n",
    "                    maxlen = j - i + 1\n",
    "        return s[maxpos: maxpos + maxlen]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubstring(self, s: str) -> str:\n",
    "        if len(s) < 2:\n",
    "            return \"\"\n",
    "        for i, c in enumerate(s):\n",
    "            # 存在任意不满足题目的割点\n",
    "            if c.upper() not in s or c.lower() not in s:\n",
    "                return max(self.longestNiceSubstring(s[:i]), self.longestNiceSubstring(s[i+1:]), key = len)\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubstring(self, s: str) -> str:\n",
    "        #|按位或，<<左移，如1左移两位为100\n",
    "        n=len(s)\n",
    "        maxPos,maxLen=0,0\n",
    "        for i in range(n):\n",
    "            lower=0\n",
    "            upper=0\n",
    "            for j in range(i,n):\n",
    "                if s[j].islower():\n",
    "                    lower|=1<<(ord(s[j])-ord('a'))\n",
    "                else:\n",
    "                    upper|=1<<(ord(s[j])-ord('A'))\n",
    "                if lower==upper and j-i+1>maxLen:\n",
    "                    maxPos=i\n",
    "                    maxLen=j-i+1\n",
    "        return s[maxPos:maxPos+maxLen]\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubstring(self, s: str) -> str:\n",
    "        def is_nice(sub):\n",
    "            return all(char.swapcase() in sub for char in sub)\n",
    "\n",
    "        longest = \"\"\n",
    "        for i in range(len(s)):\n",
    "            for j in range(i + 1, len(s)):\n",
    "                sub = s[i:j + 1]\n",
    "                if is_nice(sub) and len(sub) > len(longest):\n",
    "                    longest = sub\n",
    "        return longest"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubstring(self, s: str) -> str:\n",
    "        def check(s):\n",
    "            s = set(list(s))\n",
    "            for c in s:\n",
    "                if c.lower() not in s or c.upper() not in s:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        n, res = len(s), ''\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                if check(s[i: j + 1]) and len(s[i: j + 1]) > len(res):\n",
    "                    res = s[i: j + 1]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubstring(self, s: str) -> str:\n",
    "        if len(s) < 2:\n",
    "            return ''\n",
    "        for i, c in enumerate(s):\n",
    "            # 存在任意不满足题目的割点\n",
    "            if c.swapcase() not in s:\n",
    "                return max(self.longestNiceSubstring(s[:i]), self.longestNiceSubstring(s[i+1:]), key = len)\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubstring(self, s: str) -> str:\n",
    "        if len(s)<2:\n",
    "            return ''\n",
    "        for i, c in enumerate(s):\n",
    "            if c.upper() not in s or c.lower() not in s:\n",
    "                return max(self.longestNiceSubstring(s[:i]),self.longestNiceSubstring(s[i+1:]),key= len)\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubstring(self, s: str) -> str:\n",
    "        res = ''\n",
    "        for i in range(len(s)):\n",
    "            for j in range(i+1, len(s)+1):\n",
    "                x = set(s[i:j])\n",
    "                if all((k.islower() and k.upper() in x) or (k.isupper() and k.lower() in x) for k in x) and len(s[i:j])>len(res): res = s[i:j]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubstring(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "\n",
    "        def beauty(s, start, end):\n",
    "            daxie, xiaoxie = [0] * 26, [0] * 26\n",
    "            for c in s[start: end + 1]:\n",
    "                if 'a' <= c <= 'z':\n",
    "                    xiaoxie[ord(c) - ord('a')] = 1\n",
    "                else:\n",
    "                    daxie[ord(c) - ord('A')] = 1\n",
    "            # 子串里进行判断，分别给大写和小写数字+1，如果两个列表一样，就表示大小写字母数量一样\n",
    "            return daxie == xiaoxie\n",
    "\n",
    "        for i in range(n, -1, -1):\n",
    "            # 其实就是从两头找\n",
    "            for start in range(n):\n",
    "                end = i - 1 + start\n",
    "                print(f'i: {i},起始点: {start},终点: {end}')\n",
    "                if end>=n:\n",
    "                    break\n",
    "                if beauty(s,start,end):\n",
    "                    return s[start:end+1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubstring(self, s: str) -> str:\n",
    "        def is_nice(ss: str) -> bool:\n",
    "            return set(ss) == set(ss.lower()) | set(ss.upper())\n",
    "      \n",
    "        for length in range(len(s), -1, -1):\n",
    "            for i in range(len(s) - length + 1):\n",
    "                substr = s[i:i + length]\n",
    "                if is_nice(substr):\n",
    "                    return substr\n",
    "        return \"\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubstring(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        maxL, startIndex = 0, 0\n",
    "        for i in range(n):\n",
    "            low, capital = 0, 0\n",
    "            for j in range(i, n):\n",
    "                if s[j].islower():\n",
    "                    low |= 1 << (ord(s[j]) - ord('a'))\n",
    "                else:\n",
    "                    capital |= 1 << (ord(s[j]) - ord('A'))\n",
    "                if low == capital and maxL < j - i + 1:\n",
    "                    maxL = j - i + 1\n",
    "                    startIndex = i\n",
    "        return s[startIndex: startIndex + maxL]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def longestNiceSubstring(self, s: str) -> str:\n",
    "    b, B = ord('a'), ord('A')\n",
    "    l = len(s)\n",
    "    ret = \"\"\n",
    "    for i in range(l):\n",
    "      m, M = 0, 0\n",
    "      for j in range(i, l):\n",
    "        v = ord(s[j])\n",
    "        if v < b:\n",
    "          M = M | (1 << (v - B))\n",
    "        else:\n",
    "          m = m | (1 << (v - b))\n",
    "        # print(f\"{s[i:j + 1]} {m} {M}\")\n",
    "        if m == M:\n",
    "          if j - i + 1 > len(ret):\n",
    "            ret = s[i:j + 1]\n",
    "            # print(f\"find match {i} - {j}\")\n",
    "\n",
    "        \n",
    "    return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubstring(self, s: str) -> str:\n",
    "        maxPos, maxLen = 0, 0\n",
    "        def dfs(start, end):\n",
    "            nonlocal maxPos, maxLen\n",
    "            if start >= end:\n",
    "                return\n",
    "            lower, upper = 0, 0\n",
    "            for i in range(start, end + 1):\n",
    "                if s[i].islower():\n",
    "                    lower|= 1 << (ord(s[i]) - ord('a'))\n",
    "                else:\n",
    "                    upper|= 1 << (ord(s[i]) - ord('A'))\n",
    "            if lower == upper:\n",
    "                if end - start + 1 > maxLen:\n",
    "                    maxPos, maxLen = start, end - start + 1\n",
    "                return\n",
    "            pos, valid = start, lower & upper\n",
    "            while pos <= end:\n",
    "                start = pos\n",
    "                while pos <= end and valid & (1 << (ord(s[pos].lower()) - ord('a'))):\n",
    "                    pos += 1\n",
    "                dfs(start, pos - 1)\n",
    "                pos += 1\n",
    "        dfs(0, len(s) - 1)\n",
    "        return s[maxPos : maxPos + maxLen]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubstring(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        maxPos, maxLen = 0, 0\n",
    "        for i in range(n):\n",
    "            lower, upper = 0, 0\n",
    "            for j in range(i, n):\n",
    "                if s[j].islower():\n",
    "                    lower |= 1 << (ord(s[j]) - ord('a'))\n",
    "                else:\n",
    "                    upper |= 1 << (ord(s[j]) - ord('A'))\n",
    "                if lower == upper and j - i + 1 > maxLen:\n",
    "                    maxPos = i\n",
    "                    maxLen = j - i + 1\n",
    "        return s[maxPos: maxPos + maxLen]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubstring(self, s: str) -> str:\n",
    "        if len(s) < 2:\n",
    "            return \"\"\n",
    "        for i, c in enumerate(s):\n",
    "            if c.upper() not in s or c.lower() not in s:\n",
    "                return max(self.longestNiceSubstring(s[:i]), self.longestNiceSubstring(s[i+1:]), key = len)\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubstring(self, s: str) -> str:\n",
    "        if not s:\n",
    "            return \"\"\n",
    "        for i in range(len(s)):\n",
    "            if (s[i].lower() not in s) or (s[i].upper() not in s):\n",
    "                return max(self.longestNiceSubstring(s[:i]),self.longestNiceSubstring(s[i+1:]),key=len)\n",
    "            if i==len(s)-1:\n",
    "                return s\n",
    "                \n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubstring(self, s: str) -> str:\n",
    "        if not s:\n",
    "            return \"\"\n",
    "        for i in range(len(s)):\n",
    "            if (s[i].lower() not in s) or (s[i].upper() not in s):\n",
    "                return max(self.longestNiceSubstring(s[:i]),self.longestNiceSubstring(s[i+1:]),key=len)\n",
    "            if i==len(s)-1:\n",
    "                return s\n",
    "                \n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubstring(self, s):\n",
    "        \"\"\"\n",
    "        统计字符串中最长的完美子字符串(只含有相同的大小写字母, 且长度最长)\n",
    "        Args:   \n",
    "            s (str): 目标字符串     \n",
    "        returns (str):\n",
    "        \"\"\"\n",
    "        #处理异常情况\n",
    "        if s == None or len(s) < 2:\n",
    "            return ''\n",
    "\n",
    "        n = len(s)\n",
    "        max_pos, max_len = 0, 0\n",
    "        \n",
    "        #枚举所有可能的组合, 以i为字符串开头, j([i...n - 1])为结尾的子串是否为完美字符串\n",
    "        for i in range(n):\n",
    "            lower, upper = 0, 0 #分别使用lower, upper表示各个位置上是否出现过大小写字母, 若lower == upper, 则表示该字符串为完美字符串\n",
    "            for j in range(i, n):\n",
    "                if s[j].islower():\n",
    "                    lower |= 1 << (ord(s[j]) - ord('a'))\n",
    "                else:\n",
    "                    upper |= 1 << (ord(s[j]) - ord('A'))\n",
    "            \n",
    "                if lower == upper and j - i + 1 > max_len:\n",
    "                    max_pos = i \n",
    "                    max_len = j - i + 1\n",
    "\n",
    "        return s[max_pos: max_pos + max_len]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubstring(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        mapping_num = {}\n",
    "        mapping_pos = {}\n",
    "        for index in range(26):\n",
    "            mapping_num[chr(index + 65)] = index\n",
    "            mapping_num[chr(index + 97)] = index\n",
    "            mapping_pos[chr(index + 65)] = 0\n",
    "            mapping_pos[chr(index + 97)] = 1\n",
    "\n",
    "        res_l = res_r = None\n",
    "        max_len = 0\n",
    "\n",
    "        for target_cnt in range(1, 26):\n",
    "            l = r = 0\n",
    "            cnt_list = [[0, 0] for _ in range(26)]\n",
    "            char_cnt = 1\n",
    "            full_cnt = 0\n",
    "            num = mapping_num[s[r]]\n",
    "            pos = mapping_pos[s[r]]\n",
    "            cnt_list[num][pos] += 1\n",
    "\n",
    "            while r + 1 < n:\n",
    "                r += 1\n",
    "                num = mapping_num[s[r]]\n",
    "                pos = mapping_pos[s[r]]\n",
    "                if cnt_list[num][pos] == 0:\n",
    "                    if cnt_list[num][1 - pos] == 0:\n",
    "                        char_cnt += 1\n",
    "                    else:\n",
    "                        full_cnt += 1\n",
    "                cnt_list[num][pos] += 1\n",
    "\n",
    "                while l < r and char_cnt > target_cnt:\n",
    "                    num = mapping_num[s[l]]\n",
    "                    pos = mapping_pos[s[l]]\n",
    "                    if cnt_list[num][pos] == 1:\n",
    "                        if cnt_list[num][1 - pos] == 0:\n",
    "                            char_cnt -= 1\n",
    "                        else:\n",
    "                            full_cnt -= 1\n",
    "                    \n",
    "                    cnt_list[num][pos] -= 1\n",
    "                    l += 1\n",
    "                \n",
    "                if full_cnt == target_cnt:\n",
    "                    if r - l + 1 > max_len:\n",
    "                        max_len = r - l + 1\n",
    "                        res_l, res_r = l, r\n",
    "\n",
    "        if max_len == 0:\n",
    "            return \"\"\n",
    "        return s[res_l : res_r + 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubstring(self, s: str) -> str:\n",
    "        if len(s) < 2:\n",
    "            return \"\"\n",
    "        for i, c in enumerate(s):\n",
    "            # 存在任意不满足题目的割点\n",
    "            if c.swapcase() not in s:\n",
    "                return max(self.longestNiceSubstring(s[:i]), self.longestNiceSubstring(s[i+1:]), key = len)\n",
    "        return s\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubstring(self, s: str) -> str:\n",
    "        if len(s) < 2:\n",
    "            return \"\"\n",
    "        for i, c in enumerate(s):\n",
    "            # 存在任意不满足题目的割点\n",
    "            if c.upper() not in s or c.lower() not in s:\n",
    "                return max(self.longestNiceSubstring(s[:i]), self.longestNiceSubstring(s[i+1:]), key = len)\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubstring(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "\n",
    "        def beauty(s, start, end):\n",
    "            daxie, xiaoxie = [0] * 26, [0] * 26\n",
    "            for c in s[start: end + 1]:\n",
    "                if 'a' <= c <= 'z':\n",
    "                    xiaoxie[ord(c) - ord('a')] = 1\n",
    "                else:\n",
    "                    daxie[ord(c) - ord('A')] = 1\n",
    "            # 子串里进行判断，分别给大写和小写数字+1，如果两个列表一样，就表示大小写字母数量一样\n",
    "            return daxie == xiaoxie\n",
    "\n",
    "        for i in range(n, -1, -1):\n",
    "            # 其实就是从两头找\n",
    "            for start in range(n):\n",
    "                end = i - 1 + start\n",
    "                # print(f'i: {i},起始点: {start},终点: {end}')\n",
    "                if end>=n:\n",
    "                    break\n",
    "                if beauty(s,start,end):\n",
    "                    return s[start:end+1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubstring(self, s: str) -> str:\n",
    "        if len(s) < 2:\n",
    "            return \"\"\n",
    "        \n",
    "        for i,c in enumerate(s):\n",
    "            if any([c.upper() not in s, c.lower() not in s]):\n",
    "                return max(self.longestNiceSubstring(s[:i]), self.longestNiceSubstring(s[i+1:]), key = len)\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubstring(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        mx = 0\n",
    "        ans = ''\n",
    "        for i in range(n):\n",
    "            for j in range(i, n):\n",
    "                t = s[i:j + 1]\n",
    "                for c in t:\n",
    "                    if not (c.lower() in t and c.upper() in t):\n",
    "                        break\n",
    "                else:\n",
    "                    if j - i + 1 > mx:\n",
    "                        mx = j - i + 1\n",
    "                        ans = t \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubstring(self, s: str) -> str:\n",
    "        if len(s) < 2:\n",
    "            return \"\"\n",
    "\n",
    "        for i,j in enumerate(s):\n",
    "            if j.swapcase() not in s:\n",
    "                return max(self.longestNiceSubstring(s[:i]),self.longestNiceSubstring(s[i+1:]),key = len)\n",
    "        return s\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubstring(self, s: str) -> str:\n",
    "        if len(s) < 2:\n",
    "            return \"\"\n",
    "        for i , c in enumerate(s):\n",
    "            if c.upper() not in s or c.lower() not in s:\n",
    "                return max(self.longestNiceSubstring(s[:i]), self.longestNiceSubstring(s[i + 1:]), key = len)\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubstring(self, s: str) -> str:\n",
    "        if len(s) < 2:\n",
    "            return \"\"\n",
    "\n",
    "        for i,j in enumerate(s):\n",
    "            if j.upper() not in s or j.lower() not in s:\n",
    "                return max(self.longestNiceSubstring(s[:i]),self.longestNiceSubstring(s[i+1:]),key = len)\n",
    "        return s\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubstring(self, s: str) -> str:\n",
    "        if len(s) < 2:\n",
    "            return \"\"\n",
    "        for i, c in enumerate(s):\n",
    "            # 存在任意不满足题目的割点\n",
    "            if c.upper() not in s or c.lower() not in s:\n",
    "                return max(self.longestNiceSubstring(s[:i]), self.longestNiceSubstring(s[i+1:]), key = len)\n",
    "        return s\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubstring(self, s: str) -> str:\n",
    "        if len(s) < 2:\n",
    "            return \"\"\n",
    "        for i, c in enumerate(s):\n",
    "            if c.upper() not in s or c.lower() not in s:\n",
    "                return max(self.longestNiceSubstring(s[:i]), self.longestNiceSubstring(s[i+1:]), key = len)\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestNiceSubstring(self, s: str) -> str:\n",
    "        def check(typeNum):\n",
    "            nonlocal maxPos, maxLen\n",
    "            lowerCnt = [0] * 26\n",
    "            upperCnt = [0] * 26\n",
    "            l, r, total, cnt = 0, 0, 0, 0\n",
    "            while r < len(s):\n",
    "                idx = ord(s[r].lower()) - ord('a')\n",
    "                if s[r].islower():\n",
    "                    lowerCnt[idx] += 1\n",
    "                    if lowerCnt[idx] == 1 and upperCnt[idx] > 0:\n",
    "                        cnt += 1\n",
    "                else:\n",
    "                    upperCnt[idx] += 1\n",
    "                    if upperCnt[idx] == 1 and lowerCnt[idx] > 0:\n",
    "                        cnt += 1\n",
    "                if lowerCnt[idx] + upperCnt[idx] == 1:\n",
    "                    total += 1\n",
    "\n",
    "                while total > typeNum :\n",
    "                    idx = ord(s[l].lower()) - ord('a')\n",
    "                    if lowerCnt[idx] + upperCnt[idx] == 1:\n",
    "                        total -= 1\n",
    "                    if s[l].islower():\n",
    "                        lowerCnt[idx] -= 1\n",
    "                        if lowerCnt[idx] == 0 and upperCnt[idx] > 0:\n",
    "                            cnt -= 1\n",
    "                    else:\n",
    "                        upperCnt[idx] -= 1\n",
    "                        if upperCnt[idx] == 0 and lowerCnt[idx] > 0:\n",
    "                            cnt -= 1\n",
    "                    l += 1\n",
    "                if cnt == typeNum and r - l + 1 > maxLen:\n",
    "                    maxPos, maxLen = l, r - l + 1\n",
    "                r += 1\n",
    "        \n",
    "        maxPos, maxLen = 0, 0\n",
    "        types = len(set(s.lower()))\n",
    "        for i in range(1, types + 1):\n",
    "            check(i)\n",
    "        return s[maxPos: maxPos + maxLen]\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
